Graphics workstations include at least some form of scan conversion hardware which samples points, lines and polygons to be drawn on a display. Lower cost workstations typically utilize a single infinitely small sample per pixel, thereby resulting in primitive renderings that exhibit some aliasing artifacts. A commonly used scan conversion algorithm in such low cost systems, which results in aliased lines, is the Bresenham line algorithm. This algorithm is popular because it uses only integer arithmetic. At each iteration, the Bresenham line algorithm selects between the two pixels closest to the ideal position of the line on the grid represented by the display, based on the sign of an error term "d," turning one on pixel and leaving the other pixel off. A standard implementation of this algorithm is as follows:
______________________________________ dx=ABS(x1-x2) dy=ABS(y1-y2) d=2dy-dx // initial value of d for Octant 1 // incr1=2dy incr2=2(dy-dx) incrx1=1 incrx2=1 // always step in x // incry1=0 incry2=1 // conditional step in y // For i=1 to dx Do Begin If d&lt;0 Then Begin // Select pixel S below the line // x=x+incrx1 y=y+incry1 d=d+incr1 End Else Begin // Select pixel T above the line // x=x+incrx2 y=y+incry2 d=d+incr2 End Write.sub.-- Pixel(x,y,color) End ______________________________________
The explanatory terms "above" and "below" are used relative to the drawing octant. For example, when in octant 2, "above" means to the right of the centerline and "below" means to the left of the centerline.
Since the Bresenham algorithm causes the resulting one pixel wide line to have jagged edges, or alias artifacts, numerous techniques have been developed to remove these artifacts, or in other words, to antialias the line. A further explanation of the Bresenham line algorithm and techniques for antialiasing such lines is provided by J. D. Foley and A. Van Dam, "Fundamentals of Interactive Computer Graphics," 1983, pp. 433-437, incorporated by reference herein.
Two of the primary techniques for line antialiasing, are area sampling and multi-point sampling. In area sampling, the fraction of each pixel that is covered by a line is computed (perhaps also using multiplication by a filter function), and the resulting fractions are blended to obtain a final pixel shading for each covered or partially covered pixel. In multi-point sampling, many point samples are taken in the region of each pixel, and these samples are integrated (again, perhaps also utilizing a weighting function) to obtain pixel shading. A more detailed explanation of modern antialiasing techniques is described by J. D. Foley and A. Van Dam in "Computer Graphics - Principles and Practice" 1990, pp. 132-142, incorporated by reference herein.
An improvement to the Bresenham algorithm is described by Adrian Sfarti in "Antialiased Bresenham Lines for X Implementation", Proceedings of the 10th International Conference of the Computer Graphics Society, CG International 1992, Visual Computing - Integrating Computer Graphics with Computer Vision-, Tokyo, Japan (Jun. 26, 1992), pp. 639-659, incorporated by reference herein. In Sfarti, the standard Bresenham algorithm is extended to two pixel wide lines as follows:
______________________________________ dx=ABS(x1-x2) dy=ABS(y1-y2) e1=dy/dk e2=e1-1 d=2dy-dx // initial value of d for Octant 1 // s=e1 incr1=2dy incr2=2(dy-dx) incrx1=1 incrx2=1 // always step in x // incry1 =0 incry2=1 // conditional step in y // For i=1 to dx Do Begin If d&lt;0 Then Begin // Select pixel S below the line // x=x+incrx1 y=y+incry1 d=d+incr1 s=s+e1 End Else Begin // Select pixel T above the line // x=x+incrx2 y=y+incry2 d=d+incr2 s=s+e2 End Write.sub.-- Pixel(x,y,color) End ______________________________________
In the above code, the basic Bresenham algorithm is modified by adding the term "s," where s is the vertical distance from the line to the pixel center just below it, and the term "t," which is equal to the vertical distance from the line to the pixel center just above it. The term t is a function of s, in that t=1-s. In this improved version of the Bresenham algorithm, d=(s-t)*dx. Since s+t=1, it follows that s=(1+d/dx)/2 and t=(1-d/dx)/2. Thus, as d varies at each iteration of the line by either incr 1 or incr2, s will vary accordingly, either by e1=incr1/(2dx) or e2=incr2/(2dx). This operation allows the algorithm to avoid dividing at each iteration, since the terms e1 and e2 are constant increments that can be precomputed.
Sfarti also discusses how pixel coverages are computed, how steps can be taken to compensate for the effect of certain line slopes, and how fractional endpoints are calculated so that the line to be drawn is correctly positioned. Sfarti also discusses a technique for compensating for the effect of a third pixel intersected by the line to be drawn. As noted by Sfarti, since the two-pixel wide extension can only reference two pixels at a time, any third pixel intersected by the line would need to be neglected in order to maintain coverage formulas for the other intersected pixels. Although Sfarti discusses an attempt to compensate for neglecting the effect of the third pixel, this attempt was merely that, and does not accurately approximate the effect of the third pixel.
As discussed above, many antialiasing techniques employ filter functions. However, attempts to use hardware to incrementally compute a filter function while rendering tends to require the use of a simple filter function because better filters are too computationally expensive. Line antialiasing methods based on box postfiltering are also computationally expensive and do not produce a pixel coverage that is useful for an implementation of an alpha-buffer. An alternative approach is to pre-compute a set of filter values and store them in a look-up table, a technique described by the Gupta-Sproull algorithm (which requires integer arithmetic), and more specifically described by A. C. Barkans in "High Speed High Quality Antialiased Vector Generation", ACM Computer Graphics, Volume 24, Number 4, August 1990, incorporated herein by reference, which is directed to the use of a precomputed filter function in combination with the Bresenham algorithm.
Sfarti also describes the application of a filtering function to provide additional improvements in pixel coverage computation. Accordingly, the application of a circular cone filter 10 about the line 12, as illustrated in FIG. 1 against the grid 14, has the advantages of being rotationally symmetric and of providing for pixel coverage computation at each iteration. Unfortunately, such a filter is also computationally expensive because it requires three multiplications per iteration. As discussed by Sfarti, the advantages of this filter can be obtained, however, without its disadvantages, by precomputing the filter function and utilizing the s value in conjunction with the error term d as an index to an integral lookup table that contains the computed pixel coverages.
The distance s, as shown in FIG. 1, is used for computing pixel coverage since the convolution integral is a function of the orthogonal distance s*cosa. The computation of s therefore mimics the incremental computation of the Bresenham error term d. Since pixel coverage is a function of the distance between the center of the pixel and the line to be drawn, then d=s*cosa for 0&lt;s&lt;1. Thus, a lookup table that is indexed with s can be used to compute d.
Sfarti also indicates that error terms introduced in the improved algorithm allow for lines to be drawn with very high precision (25 bits). Although the precision of the improved algorithm would appear to be sufficient to render a reasonably accurate line, since the magnitude of s is carefully calculated, subsequent analysis of this algorithm reveals that this is not always the case. In situations where s varies between a negative and positive number, crossing through zero on various occasions, the value of s can be inaccurate enough, even at 25 bits of precision, so as to cause the sign of s to be incorrect. In such instances, pixels can be drawn on the wrong side of a line, thereby causing an artifact. In addition, if this occurred numerous times during the drawing of one line, the line would take on a twisted appearance because of the various line crossings.
It should also be noted that problems have arisen when attempts have been made to apply such line drawing and antialiasing techniques to polygonal images. The most significant of these problems relates to the accurate sampling of pixels inside the polygonal image.
Each of the aforementioned implementations of line drawing and antialiasing procedures, as well as other such procedures of which applicants are aware, do not address (1) computing pixel positions with sufficient precision to accommodate error accumulation, or (2) calculating antialiased lines while accounting for the effect of more than two pixels on that line.
One object of the invention is to improve prior implementations of line drawing procedures.
Mother object of the invention is to accommodate for the effect of three intersected pixels in each iteration of a line drawing procedure.
A further object of the invention is to improve the accuracy of line drawing procedures.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of instrumentalities and combinations particularly pointed out in the appended claims.